Buffer management is to manage the allocation and retrieval of external or embedded shared random access memory (RAM) resources of a chip. In particular, buffer management is extensively used in network devices and chips based on a store-and-forward data structure. Buffer management needs to ensure correctness of address allocation and retrieval and sufficient bandwidths for address allocation and retrieval. In present art, mature buffer management solutions include first-in first-out (FIFO) buffer management and bitmap buffer management.
In FIFO buffer management solution, the FIFO is used to store buffer addresses; all available buffer addresses are written to the FIFO at the time of initialization; addresses stored at the head of FIFO are read at the data receiving end and used to store received data; released addresses are written to the FIFO at the data transmitting end for address withdrawal. If the number of buffer addresses is n, then the quantity of consumed memory resources is calculated by the formula “r=n*log2n” in units of bits.
The principle of bitmap buffer management is to map a buffer address to a bit in a bitmap of a certain width (for example, 512 bits or 1 Kbit); idle bits are searched out for allocating idle buffer addresses. When there is a large quantity of buffer units, the bitmap buffer management solution is faced with a problem about how to search for idle bits quickly. An improved solution is to combine the bitmap and FIFO management solution. That is, when data is received, a bitmap index is firstly read from the FIFO; a bitmap is found according to the bitmap index; and idle addresses in the bitmap are allocated by a decoding logic circuit. At the data transmitting end, released physical addresses are decoded into bitmap information and written to the RAM; if all bits in a bitmap in the RAM are released completely, the index information corresponding to the bitmap is written back to the FIFO, and thus the addresses are retrieved. In the “bitmap plus FIFO” buffer management solution, if the total number of buffer addresses is “n=x*y”, the quantity of consumed resources is calculated by the formula “r=n+y*log2y” in units of bit, where: “n” indicates the total number of RAM resources; “x” indicates the width of the bitmap; and “y*log2y” indicates the number of FIFO resources.